package 力扣;

import java.util.LinkedList;
import java.util.List;

/**
 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
 说明：
 分隔时可以重复使用字典中的单词。
 你可以假设字典中没有重复的单词。
 示例 1：
 输入:
 s = "catsanddog"
 wordDict = ["cat", "cats", "and", "sand", "dog"]
 输出:
 [
   "cats and dog",
   "cat sand dog"
 ]
 示例 2：
 输入:
 s = "pineapplepenapple"
 wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
 输出:
 [
   "pine apple pen apple",
   "pineapple pen apple",
   "pine applepen apple"
 ]
 解释: 注意你可以重复使用字典中的单词。
 示例 3：
 输入:
 s = "catsandog"
 wordDict = ["cats", "dog", "sand", "and", "cat"]
 输出:
 []
 */
public class _140单词拆分_II {

    public List<String> wordBreak(String s, List<String> wordDict) {

        int len = s.length();
        LinkedList<String>[] dp = new LinkedList[len + 1];
        LinkedList init = new LinkedList();
        init.add("");
        dp[0] = init;
        for (int i = 1; i <=len ; i++) {
            LinkedList<String> list = new LinkedList<>();
            for (int j = 0; j < i ; j++) {

                String temp = s.substring(j, i);
                if( dp[j].size()>0 && wordDict.contains(temp)){
                        //遍历dp[j] , dp[i]的值为 dp[j] 中的值 + temp
                    for( String str : dp[j]){
                        list.add(str+(str.equals("")?"":" ")+temp);
                    }
                }
            }
            dp[i] = list;
        }

        return dp[len];
    }
}
